Using Euclids Extended Algorithm:
Calculate x and y in Bézout's Identity
using (99,903070)
For 2 numbers a and b and divisor d:
ax + by = d
a math | a | b math | b | d math | d | k math | k |
---|---|---|---|---|---|---|---|
Set to 1 | 1 | Set to 0 | 0 | 99 | |||
Set to 0 | 0 | Set to 1 | 1 | 903070 | Quotient of 99/903070 | 0 | |
1 - (0 x 0) | 1 | 0 - (0 x 1) | 0 | Remainder of 99/903070 | 99 | Quotient of 903070/99 | 9121 |
0 - (9121 x 1) | -9121 | 1 - (9121 x 0) | 1 | Remainder of 903070/99 | 91 | Quotient of 99/91 | 1 |
1 - (1 x -9121) | 9122 | 0 - (1 x 1) | -1 | Remainder of 99/91 | 8 | Quotient of 91/8 | 11 |
-9121 - (11 x 9122) | -109463 | 1 - (11 x -1) | 12 | Remainder of 91/8 | 3 | Quotient of 8/3 | 2 |
9122 - (2 x -109463) | 228048 | -1 - (2 x 12) | -25 | Remainder of 8/3 | 2 | Quotient of 3/2 | 1 |
-109463 - (1 x 228048) | -337511 | 12 - (1 x -25) | 37 | Remainder of 3/2 | 1 | Quotient of 2/1 | 2 |
228048 - (2 x -337511) | 903070 | -25 - (2 x 37) | -99 | Remainder of 2/1 | 0 | Quotient of 1/0 | 0 |
a = -337511 and b = 37
ax + by = gcd(a,b)
99x + 903070y = gcd(99